Exercise: Equivalent Binary Trees
https://tour.golang.org/concurrency/8
木のサイズを先にチェックしてそのサイズ分だけチャネルから受け取る方法を考えた。
でもサイズを先にチェックするのではなくサーチし終わった時にchannelをcloseする方が使いやすい。そのようにするにはどうしたら良いだろうか？
code: precalcTreeSize.go
package main
import (
"fmt"
"golang.org/x/tour/tree"
)
/*
type Tree struct {
Left *Tree
Value int
Right *Tree
}
*/
// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
ch <- t.Value
if t.Left != nil {
Walk(t.Left, ch)
}
if t.Right != nil {
Walk(t.Right, ch)
}
}
// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
s1, s2 := Size(t1), Size(t2)
if s1 != s2 {
return false
}
ch1 := make(chan int)
ch2 := make(chan int)
m1 := make(mapintint)
m2 := make(mapintint)
go Walk(t1, ch1)
go Walk(t2, ch2)
for i := 0; i < s1+s2; i++ {
select {
case v := <-ch1:
m1v++
case v := <-ch2:
m2v++
}
}
for k := range m1 {
if m1k != m2k {
return false
}
}
return true
}
func Size(t *tree.Tree) (result int) {
result = 1
if t.Left == nil && t.Right == nil {
return
}
if t.Left != nil {
result += Size(t.Left)
}
if t.Right != nil {
result += Size(t.Right)
}
return
}
func main() {
testWalk()
testSize()
testSame()
}
func testSame() {
t1 := tree.New(1)
t2 := tree.New(1)
t3 := tree.New(2)
fmt.Println("t1 should same as t2 where Same(t1,t2) =", Same(t1, t2))
fmt.Println("t1 should not same as t3 where Same(t1,t3) =", Same(t1, t3))
}
func testSize() {
t := tree.New(1)
fmt.Println("Size =", Size(t))
}
func testWalk() {
t := tree.New(1)
ch := make(chan int)
go Walk(t, ch)
for i := 0; i < 10; i++ {
v := <-ch
fmt.Println(v)
}
}